package chapter25;

import java.util.Arrays;

/**
 * 所有节点对的最短路径-FloydWarshall
 */
public class FloydWarshall {

    public static int[][] floydWarshall(int[][] W) {
        int n = W.length;
        int[][][] D = new int[n+1][n][n];
        D[0] = W;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int a = D[k][i][k];
                    int b = D[k][k][j];
                    int c = Integer.MAX_VALUE;
                    if (a != Integer.MAX_VALUE && b != Integer.MAX_VALUE) {
                        c = a + b;
                    }
                    D[k+1][i][j] = Math.min(D[k][i][j], c);
                }
            }
        }
        return D[n];
    }

    public static int[][] transitiveClosure(Graph G) {
        int n = G.numVertexes;
        int[][][] T = new int[n][n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || G.adj[i][j] == 1) {
                    T[0][i][j] = 1;
                }
            }
        }
        for (int k = 1; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    T[k][i][j] = T[k - 1][i][j] | (T[k - 1][i][k] & T[k - 1][k][j]);
                }
            }
        }
        return T[n - 1];
    }

    public static class Graph {
        public int[][] adj;
        public int numVertexes;
        public int numEdges;

        @Override
        public String toString() {
            return "Graph{" +
                    "adj=" + Arrays.toString(adj) +
                    ", numVertexes=" + numVertexes +
                    ", numEdges=" + numEdges +
                    '}';
        }
    }
}
